package week06

// 1143. 最长公共子序列
// https://leetcode-cn.com/problems/longest-common-subsequence/

func longestCommonSubsequence(text1 string, text2 string) int {
	var m = len(text1)
	var n = len(text2)
	// 上面补一行，左边补一列，减法不用判断边界
	var f = make([][]int, m+1)
	for i := 0; i < len(f); i++ {
		f[i] = make([]int, n+1)
	}
	// text1[i] == text2[j]: f[i][j] = f[i-1][j-1] + 1
	// text1[i] /= text2[j]: f[i][j] = max(f[i-1][j], f[i][j-1])
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] { // 从1开始，这里减1
				f[i][j] = f[i-1][j-1] + 1
			} else {
				f[i][j] = max(f[i-1][j], f[i][j-1])
			}
		}
	}
	return f[m][n]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}